package br.ufrgs.ga.fitness;

import java.security.InvalidParameterException;
import java.util.List;

import br.ufrgs.tsp.model.ICity;

/**
 * Encapsulates the logic of a fitness calculator for a TSP genetic algorithm instance.
 * 
 * @author mineiro
 * 
 */
public class TspTourFitnessCalculator implements FitnessCalculator {

	/**
	 * The best value of that a valid TSP tour can have.
	 */
	public static final int TSP_BEST_FITNESS_VALUE = 0;
	
	/**
	 * Initial configuration of cities in a TSP instance.
	 */
	private List<ICity> citiesConfiguration;
	
	/**
	 * Initialize the calculator.<br/>
	 * Throw an exception if the parameter is null or the list is empty.
	 * @param citiesConfiguration Initial configuration of cities in a TSP instance.
	 */
	public TspTourFitnessCalculator(List<ICity> citiesConfiguration) {
		if (citiesConfiguration == null || citiesConfiguration.isEmpty())
			throw new InvalidParameterException("The citiesConfiguration list cannot be null or empty.");
		
		this.citiesConfiguration = citiesConfiguration;
	}
	
	@Override
	public Integer calculate(String tour) {
		if (tour.length() > citiesConfiguration.size() + 1) {
			throw new InvalidParameterException("The tour string must have length " + citiesConfiguration.size() + 1);
		}
		
		int[] citiesVisitCount = calculateCitiesVisitsCount(tour);
		
		int fitnessValueValidTour = calculateFitnessValueForValidTour(tour);
		int fitnessValueTSPTour = calculateFitnessValueForTSPTour(tour, citiesVisitCount);
		return fitnessValueValidTour + fitnessValueTSPTour;
	}

	/**
	 * Calculates the fitness of a TSP tour. A valid TSP tour is one that all cities are
	 * visited at most one time, except for the tour start city that is visited twice.
	 * 
	 * @param tour string that represents the tour
	 * @param citiesVisitCount vector where it's index represents a city identifier and it's values the count of visits at that city
	 * @return the tour fitness value.<br/>
	 * 1) A valid tour is one that respects the link between cities. But, a valid TSP Tour is one that in addition, visit just one time each city, except for the tour start city that is visited twice (start and end of the tour).<br/>
	 * 2) TSP tours have fitness equals to 0 (zero), this is the best fitness that a tour can have. Tours that are not TSP ones, have fitness < 0 (zero).
	 */
	public int calculateFitnessValueForTSPTour(String tour, int[] citiesVisitCount) {
		if (tour.length() > citiesConfiguration.size() + 1) {
			throw new InvalidParameterException("The tour string must have length " + citiesConfiguration.size() + 1);
		}
		
		int fitness = 0;
		int startCity = Integer.parseInt(tour.substring(0, 1));
		int endCity = Integer.parseInt(tour.substring(tour.length() - 1));

		// Case that the tour start city is not the tour end city.
		if (startCity != endCity) {
			fitness--;
		}
		
		// Calculates the fitness of the tour corresponded by the dnaStrand string.
		for (int i = 0; i < citiesVisitCount.length; i++) {

			if (citiesVisitCount[i] > 2 || citiesVisitCount[i] == 0) {
				fitness--;
			} else if (citiesVisitCount[i] == 2) {
				// Just the tour start city is visited 2 times.
				if (!(isTourStartCity(i, startCity) && isTourEndCity(i, endCity))) {
					// It means that the city with 2 visits is not the start and end city of the tour,
					// what is not valid, so, it is not a good tour...
					fitness--;
				}
			}
		}

		return fitness;
	}
	
	/**
	 * Calculate the fitness of a tour.<br/>
	 * If the tour is a valid one, that is, the tour respects the linke between cities, then, it's fitness is equals to zero. Otherwise, the fitness will be < 0 (zero).<br/>
	 * The fitness is decreased by one for every invalid city link found in the TSP instance configuration.
	 * @param tour an instance of a tour, ex.: 012435, where the numbers are cities indentifiers.
	 * @return the tour fitness
	 */
	public int calculateFitnessValueForValidTour(String tour) {
		if (tour.length() > citiesConfiguration.size() + 1) {
			throw new InvalidParameterException("The tour string must have length " + citiesConfiguration.size() + 1);
		}

		int fitness = 0;
		for (int i = 0; i < tour.length() - 1; i++) {
			int srcCityIndex = Integer.parseInt(tour.substring(i, i + 1));
			int destCityIndex = Integer.parseInt(tour.substring(i + 1, i + 2));
			ICity srcCity = citiesConfiguration.get(srcCityIndex);
			ICity destCity = citiesConfiguration.get(destCityIndex);
			if (!srcCity.hasNeigboard(destCity)) {
				fitness--;
			}
		}
		
		return fitness;
	}

	/**
	 * Calculates how many times a city is visited.
	 * 
	 * @param tour represents a tour
	 * @return vector where it's index represents a city identifier and it's values the count of visits at that city.
	 */
	public int[] calculateCitiesVisitsCount(String tour) {
		if (tour.length() > citiesConfiguration.size() + 1) {
			throw new InvalidParameterException("The tour string must have length " + citiesConfiguration.size() + 1);
		}
		
		// The last city in a valid tour is equals to the first one, so the
		// citiesVisitCount vector must has length of the tour size.
		int[] citiesVisitCount = getInitializedCitiesVisitCountVector(tour.length() - 1);

		// Counts how many times a city is visited in the tour corresponded by
		// the dnaStrand string.
		for (int currentVisitedCityIndex = 0; currentVisitedCityIndex < tour.length(); currentVisitedCityIndex++) {
			int currentVisitedCityId = Integer.parseInt(Character.toString(tour.charAt(currentVisitedCityIndex)));
			citiesVisitCount[currentVisitedCityId]++;
		}

		return citiesVisitCount;
	}

	/**
	 * Creates an zero initialized vector where it indexes represents cities identifiers.
	 * @param citiesCount cities count
	 * @return the zero initialized vector.
	 */
	private int[] getInitializedCitiesVisitCountVector(int citiesCount) {
		int[] citiesVisitCount = new int[citiesCount];
		for (int i = 0; i < citiesCount; i++) {
			citiesVisitCount[i] = 0;
		}

		return citiesVisitCount;
	}

	/**
	 * Verify if a city id (<code>i</code>) is the start of the tour.
	 * 
	 * @param i a city id.
	 * @param startCityId tour start city id.
	 * @return <code>true</code> id the city of id <code>i</code> is the start of the tour, <code>false</code> otherwise.
	 */
	private boolean isTourStartCity(int i, int startCityId) {
		return i == startCityId;
	}

	/**
	 * Verify if a city id (<code>i</code>) is the end of the tour.
	 * @param i a city id
	 * @param endCityId tour end city id.
	 * @return <code>true</code> id the city of id <code>i</code> is the end of the tour, <code>false</code> otherwise.
	 */
	private boolean isTourEndCity(int i, int endCityId) {
		return i == endCityId;
	}
}
